{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Author: OMKAR PATHAK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Linked Lists"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### What are Linked Lists?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A linked List is a data structure used for storing collections of data. A linked list has the following properties.\n",
    "* Successive elements a re connected by pointers\n",
    "* The last element points to NULL(__None__ in Python)\n",
    "* Can grow or shrink in size during execution of a program\n",
    "* Can be made just as long as required (until systems memory exhausts)\n",
    "* Does not waste memory space (but takes some extra memory for pointers)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Properties of Linked Lists:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Linked lists are linear data structures that hold data in individual objects called nodes. These nodes hold both the data and a reference to the next node in the list.\n",
    "* Each node contains a value, and a reference (also known as a pointer) to the next node. The last node, points to a null node. This means the list is at its end.\n",
    "* Linked lists offer some important advantages over other linear data structures. Unlike arrays, they are a dynamic data structure, resizable at run-time. Also, the insertion and deletion operations are efficient and easily implemented.\n",
    "* However, linked lists do have some drawbacks. Unlike arrays, linked lists aren't fast at finding the __n__th item.To find a node at position __n__, you have to start the search at the first node in the linked list, following the path of references  times. Also, because linked lists are inherently sequential in the forward direction, operations like backwards traversal--visiting every node starting from the end and ending in the front--is especially cumbersome. (__Only sequential search possible__)\n",
    "* Additionally, linked lists use more storage than the array due to their property of referencing the next node in the linked list.\n",
    "* Finally, unlike an array whose values are all stored in contiguous memory, a linked list's nodes are at arbitrary, possibly far apart locations in memory."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Common Operations:\n",
    "* Insert           \n",
    "* Insert at end\n",
    "* Insert at beginning\n",
    "* Insert between\n",
    "* Delete                \n",
    "* Search                \n",
    "* Indexing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Time Complexity:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Insertion: O(1)\n",
    "* Deletion: O(1)\n",
    "* Indexing: O(n)\n",
    "* Searching: O(n)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
